package mo.leetcode_top;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class L1104 {

    public List<Integer> pathInZigZagTree(int label) {
        if (label == 1) {
            return Collections.singletonList(1);
        }
        List<Integer> ans = new ArrayList<>();

        int start = 0;
        int end = 0;
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            start = (int) Math.pow(2, i-1);
            end = (int) Math.pow(2, i)-1;
            if (label >=  start && label <= end) {
                break;
            }
        }

        ans.add(0, label);
        while (label != 1) {
            int symmetric = getSymmetric(label, start, end);
            label = symmetric / 2;
            ans.add(0, label);
            start = start / 2;
            end = end / 2;
        }

        return ans;
    }


    private int getSymmetric(int label, int start, int end) {
        return (end - label) + start;
    }

}
